        <!DOCTYPE html>
        <html>
        <head>
                <meta charset="utf-8">
        <title>DynamicTree class / box2d_html Library / Dart Documentation</title>
        <link rel="stylesheet" type="text/css"
            href="../styles.css">
        <link href="http://fonts.googleapis.com/css?family=Open+Sans:400,600,700,800" rel="stylesheet" type="text/css">
        <link rel="shortcut icon" href="../favicon.ico">
        
        </head>
        <body data-library="box2d_html" data-type="DynamicTree">
        <div class="page">
        <div class="header">
          <a href="../index.html"><div class="logo"></div></a>
          <a href="../index.html">Dart Documentation</a>
         &rsaquo; <a href="../box2d_html.html">box2d_html</a> &rsaquo; <a href="../box2d_html/DynamicTree.html">DynamicTree</a>        <div id="search-box">
          <input type="search" name="q" id="q" autocomplete="off"
              class="search-input" placeholder="Search API">
        </div>
        
      </div>
      <div class="drop-down" id="drop-down"></div>
      
        <div class="nav">
        
</div>
<div class="content">
        <h2><strong>DynamicTree</strong>
          class
        </h2>
        
<button id="show-inherited" class="show-inherited">Hide inherited</button>
<div class="doc">
<p>A dynamic tree arranges data in a binary tree to accelerate
queries such as volume queries and ray casts. Leafs are proxies
with an AxisAlignedBox. In the tree we expand the proxy box by
Settings.BOUNDING<em>BOX</em>EXTENSION so that the proxy box is bigger than the
client object. This allows the client object to move by small amounts without
triggering a tree update.</p>
<pre class="source">
class DynamicTree {
  static const int MAX_STACK_SIZE = 64;

  /** The number of nodes to add to the node stack if its empty. */
  static const int _DEFAULT_NODE_ADDITION = 6;

  DynamicTreeNode _root;
  /** Current number of active nodes */
  int _nodeCount;
  DynamicTreeNode _lastLeaf;
  int _insertionCount;
  int _path;

  final Queue&lt;DynamicTreeNode&gt; _nodeStack;
  final List&lt;Vector&gt; _drawVectors;
  /** Monotonically increasing count used to uniquely identify nodes. */
  int _nodeCounter;

  /**
   *  Temporary objects that are used privately and are initialized at
   *  construction. These are used instead of creating new objects during tree
   *  operation.
   */
  final Vector _tempVector;
  final AxisAlignedBox _tempBox;
  final Vector center;
  final Vector deltaOne;
  final Vector deltaTwo;

  /**
   * Constructs a new DynamicTree.
   */
  DynamicTree() :
    _root = null,
    _nodeCount = 0,
    _insertionCount = 0,
    _path = 0,
    _lastLeaf = null,
    _drawVectors = new List&lt;Vector&gt;(4),
    _nodeCounter = 0,
    _tempVector = new Vector(),
    _tempBox = new AxisAlignedBox(),
    _nodeStack = new Queue&lt;DynamicTreeNode&gt;(),
    // Pool objects.
    center = new Vector(),
    deltaOne = new Vector(),
    deltaTwo = new Vector() {

    // Place new vectors in the draw vectors array.
    for (int i = 0; i &lt; _drawVectors.length; ++i)
      _drawVectors[i] = new Vector();
  }

  /**
   * Create a proxy. Provides a tight fitting axis aligned box
   * and a userData pointer.
   */
  DynamicTreeNode createProxy(AxisAlignedBox box, Object userData) {
    DynamicTreeNode proxy = _allocateNode();

    // Fatten the bounding box.
    proxy.box.lowerBound.x = box.lowerBound.x - Settings.BOUNDING_BOX_EXTENSION;
    proxy.box.lowerBound.y = box.lowerBound.y - Settings.BOUNDING_BOX_EXTENSION;
    proxy.box.upperBound.x = box.upperBound.x + Settings.BOUNDING_BOX_EXTENSION;
    proxy.box.upperBound.y = box.upperBound.y + Settings.BOUNDING_BOX_EXTENSION;

    // Assign the given user Data to the proxy node.
    proxy.userData = userData;

    // Insert the proxy node on the tree.
    _insertLeaf(proxy);

    // TODO(dominich): The iteration count should be enough to hit all nodes in the 
    // tree but not too large such that it wastes time. This could be tuned.
    int iterationCount = _nodeCount &gt;&gt; 4;
    int tryCount = 0;
    int height = computeHeightFromRoot();
    while (height &gt; 64 &amp;&amp; tryCount &lt; 10) {
      rebalance(iterationCount);
      height = computeHeightFromRoot();
      ++tryCount;
    }

    return proxy;
  }

  /** Destroys the given proxy. */
  void destroyProxy(DynamicTreeNode toDestroy) {
    // The given proxy must not be null and must be a leaf.
    assert(toDestroy != null);
    assert(toDestroy.isLeaf);

    // Remove and free the proxy.
    _removeLeaf(toDestroy);
    _freeNode(toDestroy);
  }

  /**
   * Move a proxy with a swept AABB. If the proxy has moved outside of its
   * fattened AABB, then the proxy is removed from the tree and re-inserted.
   * Otherwise, the function returns immediately.
   *
   * Returns true if the given proxy was re-inserted.
   */
  bool moveProxy(DynamicTreeNode argProxy, AxisAlignedBox argBox,
      Vector displacement) {
    // The given proxy must not be null and must be a leaf.
    assert (argProxy != null);
    assert (argProxy.isLeaf);

    // If the given proxies box contains the given box, then return right away.
    if (argProxy.box.contains(argBox))
      return false;

    // Remove the proxy from the tree.
    _removeLeaf(argProxy);

    // Extend the bounding box.
    argBox.lowerBound.x -= Settings.BOUNDING_BOX_EXTENSION;
    argBox.lowerBound.y -= Settings.BOUNDING_BOX_EXTENSION;
    argBox.upperBound.x += Settings.BOUNDING_BOX_EXTENSION;
    argBox.upperBound.y += Settings.BOUNDING_BOX_EXTENSION;

    // Predict bounding box displacement.
    _tempVector.setFrom(displacement);
    _tempVector.mulLocal(Settings.BOUNDING_BOX_MULTIPLIER);
    if (_tempVector.x &lt; 0)
      argBox.lowerBound.x += _tempVector.x;
    else
      argBox.upperBound.x += _tempVector.x;

    if (_tempVector.y &lt; 0)
      argBox.lowerBound.y += _tempVector.y;
    else
      argBox.upperBound.y += _tempVector.y;

    argProxy.box.setFrom(argBox);

    // Insert the argument proxy and return true.
    _insertLeaf(argProxy);
    return true;
  }

  /** Allocates a new node and increases the node count. */
  DynamicTreeNode _allocateNode() {
    // If node stack is empty, add nodes to it.
    if (_nodeStack.isEmpty()) {
      for (int i = 0; i &lt; _DEFAULT_NODE_ADDITION; ++i)
        _nodeStack.addFirst(new DynamicTreeNode._construct());
    }

    DynamicTreeNode node = _nodeStack.removeFirst();
    node.parent = null;
    node.childOne = null;
    node.childTwo = null;
    node.userData = null;
    node.key = _nodeCounter;
    ++_nodeCounter;
    ++_nodeCount;
    return node;
  }

  /**
   * Queries a bounding box for overlapping proxies. The callback class is
   * called for each proxy that overlaps the given bounding box.
   */
  void query(TreeCallback callback, AxisAlignedBox argBox) {
    _query(callback, argBox, _root, 1);
  }

  // Private recursive query function. Returns true if should proceed.
  bool _query(TreeCallback callback, AxisAlignedBox argBox, DynamicTreeNode
      node, int count) {
    // If given node is null, get out of here and continue recursing.
    if (node == null)
      return true;

    if (AxisAlignedBox.testOverlap(argBox, node.box)) {

      if (node.isLeaf) {
        if (!callback.treeCallback(node))
          return false;
      } else {
        if (count &lt; MAX_STACK_SIZE) {
          ++count;
          if (!_query(callback, argBox, node.childOne, count))
            return false;
        }

        if (count &lt; MAX_STACK_SIZE) {
          ++count;
          if (!_query(callback, argBox, node.childTwo, count))
            return false;
        }
      }
    }
    return true;
  }

  /** Inserts a leaf into the tree. */
  void _insertLeaf(DynamicTreeNode node) {
    // Increment insertion count.
    ++_insertionCount;

    // If nothing in the tree, make given node the root.
    if (_root == null) {
      _root = node;
      node.parent = null;
      return;
    }

    // Find the best sibling for the given node. Start looking at the root.
    center.setFrom(node.box.center);
    DynamicTreeNode sibling = _root;

    DynamicTreeNode childOne, childTwo;

    // Search through the tree until finding a suitable leaf to be the node's
    // sibling.
    if (!sibling.isLeaf) {
      do {
        childOne = sibling.childOne;
        childTwo = sibling.childTwo;

        // Find the absolute difference between the center of the bounding box for
        // the node we are inserting and the center's of the bounding boxes of the
        // two children.
        deltaOne.setFrom(childOne.box.center);
        deltaTwo.setFrom(childTwo.box.center);
        deltaOne.subLocal(center).absLocal();
        deltaTwo.subLocal(center).absLocal();

        num normOne = deltaOne.x + deltaOne.y;
        num normTwo = deltaTwo.x + deltaTwo.y;

        sibling = (normOne &lt; normTwo ? childOne : childTwo);

      } while (sibling.isLeaf == false);
    }

    // Create a new parent for the siblings. Make this node the child of
    // the current parent node.
    DynamicTreeNode node1 = sibling.parent;
    DynamicTreeNode node2 = _allocateNode();
    node2.parent = node1;
    node2.userData = null;
    node2.box.setFromCombination(node.box, sibling.box);

    // If the old parent wasn't the root node...
    if (node1 != null) {
      // If the sibling was the first child, make the new parent the first child
      // of the old parent. Otherwise, make it the second.
      if (sibling.parent.childOne === sibling)
        node1.childOne = node2;
      else
        node1.childTwo = node2;

      // Set the new parent's children.
      node2.childOne = sibling;
      node2.childTwo = node;
      sibling.parent = node2;
      node.parent = node2;

      // Build up the axis-aligned boxes in case we expanded them out.
      do {
        // If the old parent's box contains the new parent's box, leave.
        if (node1.box.contains(node2.box))
          break;

        // Set the old parent's box to the combination of it's new
        // children's boxes.
        node1.box.setFromCombination(node1.childOne.box, node1.childTwo.box);
        node2 = node1;
        node1 = node1.parent;
      } while (node1 != null);
    } else {
      node2.childOne = sibling;
      node2.childTwo = node;
      sibling.parent = node2;
      node.parent = node2;
      _root = node2;
    }
  }

  /** Removes the given leaf from the tree. */
  void _removeLeaf(DynamicTreeNode argNode) {
    // If asked to remove the root, set the root to null. If that was also the
    // last leaf, then set lastLeaf to null as well.
    if (argNode === _root) {
      _root = null;
      if (_lastLeaf === argNode) {
        _lastLeaf = null;
      }
      return;
    }

    DynamicTreeNode node2 = argNode.parent;
    DynamicTreeNode node1 = node2.parent;
    DynamicTreeNode sibling;

    // Find the sibling of the node to remove.
    sibling = (node2.childOne === argNode ? node2.childTwo : node2.childOne);

    // If the grandparent node of the node to remove isn't null, destroy the
    // parent node and connect the grandparent node directly to the sibling.
    if (node1 != null) {
      if (node1.childOne === node2)
        node1.childOne = sibling;
      else
        node1.childTwo = sibling;

      sibling.parent = node1;

      // Return the target's parent node to the node pool.
      _freeNode(node2);

      // Adjust the bounds of the boxes belong to the node-to-remove's
      // ancestors.
      while (node1 != null) {
        // Set the current node's box to a combination of it's children's boxes.
        // If this combination is contained within it's previous box, then exit
        // the loop. Otherwise, continue adjusting the bounds of the ancestor's
        // boxes.
        _tempBox.setFrom(node1.box);
        node1.box.setFromCombination(node1.childOne.box, node1.childTwo.box);
        if (_tempBox.contains(node1.box)) {
          break;
        }

        node1 = node1.parent;
      }
    } else {
      // The parent node was the root! So set the root to be the sibling.
      _root = sibling;
      sibling.parent = null;
      _freeNode(node2);
    }

    // If we just removed the last leaf, the root is the new last leaf.
    if (_lastLeaf === argNode) {
      _lastLeaf = _root;
    }
  }

  /** Computes the height of the overall tree. */
  int computeHeightFromRoot() =&gt; _computeHeight(_root);

  /** Computes the height of the given tree. */
  int _computeHeight(DynamicTreeNode node) {
    if (node == null)
      return 0;

    int heightOne = _computeHeight(node.childOne);
    int heightTwo = _computeHeight(node.childTwo);
    return 1 + Math.max(heightOne, heightTwo);
  }


  /**
   * Rebalances the tree for the given number of iterations. Does a post-order
   * traversal of the tree. If given enough iterations it will hit all nodes of
   * the tree. Starts at the last reinserted leaf.
   */
  void rebalance(int iterations) {
    if (_root == null)
      return;

    DynamicTreeNode current;
    for (int i = 0; i &lt; iterations; ++i) {
      current = _root;

      int bit = 0;
      while (!current.isLeaf) {
        int goLeft = (_path &gt;&gt; bit) &amp; 1;
        current = (goLeft == 0 ? current.childOne : current.childTwo);

        bit = (bit + 1) &amp; 31;
      }

      ++_path;

      _removeLeaf(current);
      _insertLeaf(current);
    }
  }

  /** Returns a node to the node pool. */
  void _freeNode(DynamicTreeNode node) {
    assert(node != null);
    assert(_nodeCount &gt; 0);
    _nodeStack.addFirst(node);
    --_nodeCount;
  }
}
</pre>
</div>
<div>
<h3>Constructors</h3>
<div class="method"><h4 id="DynamicTree">
<button class="show-code">Code</button>
new <strong>DynamicTree</strong>() <a class="anchor-link" href="#DynamicTree"
              title="Permalink to DynamicTree.DynamicTree">#</a></h4>
<div class="doc">
<p>Constructs a new DynamicTree.</p>
<pre class="source">
DynamicTree() :
  _root = null,
  _nodeCount = 0,
  _insertionCount = 0,
  _path = 0,
  _lastLeaf = null,
  _drawVectors = new List&lt;Vector&gt;(4),
  _nodeCounter = 0,
  _tempVector = new Vector(),
  _tempBox = new AxisAlignedBox(),
  _nodeStack = new Queue&lt;DynamicTreeNode&gt;(),
  // Pool objects.
  center = new Vector(),
  deltaOne = new Vector(),
  deltaTwo = new Vector() {

  // Place new vectors in the draw vectors array.
  for (int i = 0; i &lt; _drawVectors.length; ++i)
    _drawVectors[i] = new Vector();
}
</pre>
</div>
</div>
</div>
<div>
<h3>Static Properties</h3>
<div class="field"><h4 id="MAX_STACK_SIZE">
<button class="show-code">Code</button>
const int         <strong>MAX_STACK_SIZE</strong> <a class="anchor-link"
            href="#MAX_STACK_SIZE"
            title="Permalink to DynamicTree.MAX_STACK_SIZE">#</a>
        </h4>
        <div class="doc">
<pre class="source">
static const int MAX_STACK_SIZE = 64;
</pre>
</div>
</div>
</div>
<div>
<h3>Properties</h3>
<div class="field"><h4 id="center">
<button class="show-code">Code</button>
final <a href="../box2d_html/Vector.html">Vector</a>         <strong>center</strong> <a class="anchor-link"
            href="#center"
            title="Permalink to DynamicTree.center">#</a>
        </h4>
        <div class="doc">
<pre class="source">
final Vector center;
</pre>
</div>
</div>
<div class="field"><h4 id="deltaOne">
<button class="show-code">Code</button>
final <a href="../box2d_html/Vector.html">Vector</a>         <strong>deltaOne</strong> <a class="anchor-link"
            href="#deltaOne"
            title="Permalink to DynamicTree.deltaOne">#</a>
        </h4>
        <div class="doc">
<pre class="source">
final Vector deltaOne;
</pre>
</div>
</div>
<div class="field"><h4 id="deltaTwo">
<button class="show-code">Code</button>
final <a href="../box2d_html/Vector.html">Vector</a>         <strong>deltaTwo</strong> <a class="anchor-link"
            href="#deltaTwo"
            title="Permalink to DynamicTree.deltaTwo">#</a>
        </h4>
        <div class="doc">
<pre class="source">
final Vector deltaTwo;
</pre>
</div>
</div>
<div class="field inherited"><h4 id="runtimeType">
<button class="show-code">Code</button>
final Type         <strong>runtimeType</strong> <a class="anchor-link"
            href="#runtimeType"
            title="Permalink to DynamicTree.runtimeType">#</a>
        </h4>
        <div class="inherited-from">inherited from Object </div><div class="doc">
<p>A representation of the runtime type of the object.</p>
<pre class="source">
external Type get runtimeType;
</pre>
</div>
</div>
</div>
<div>
<h3>Operators</h3>
<div class="method inherited"><h4 id="==">
<button class="show-code">Code</button>
bool <strong>operator ==</strong>(other) <a class="anchor-link" href="#=="
              title="Permalink to DynamicTree.operator ==">#</a></h4>
<div class="inherited-from">inherited from Object </div><div class="doc">
<p>The equality operator.</p>
<p>The default behavior for all <code>Object</code>s is to return true if and
only if <code>this</code> and 
<span class="param">other</span> are the same object.</p>
<p>If a subclass overrides the equality operator it should override
the <code>hashCode</code> method as well to maintain consistency.</p>
<pre class="source">
bool operator ==(other) =&gt; identical(this, other);
</pre>
</div>
</div>
</div>
<div>
<h3>Methods</h3>
<div class="method"><h4 id="computeHeightFromRoot">
<button class="show-code">Code</button>
int <strong>computeHeightFromRoot</strong>() <a class="anchor-link" href="#computeHeightFromRoot"
              title="Permalink to DynamicTree.computeHeightFromRoot">#</a></h4>
<div class="doc">
<p>Computes the height of the overall tree.</p>
<pre class="source">
int computeHeightFromRoot() =&gt; _computeHeight(_root);
</pre>
</div>
</div>
<div class="method"><h4 id="createProxy">
<button class="show-code">Code</button>
<a href="../box2d_html/DynamicTreeNode.html">DynamicTreeNode</a> <strong>createProxy</strong>(<a href="../box2d_html/AxisAlignedBox.html">AxisAlignedBox</a> box, Object userData) <a class="anchor-link" href="#createProxy"
              title="Permalink to DynamicTree.createProxy">#</a></h4>
<div class="doc">
<p>Create a proxy. Provides a tight fitting axis aligned box
and a userData pointer.</p>
<pre class="source">
DynamicTreeNode createProxy(AxisAlignedBox box, Object userData) {
  DynamicTreeNode proxy = _allocateNode();

  // Fatten the bounding box.
  proxy.box.lowerBound.x = box.lowerBound.x - Settings.BOUNDING_BOX_EXTENSION;
  proxy.box.lowerBound.y = box.lowerBound.y - Settings.BOUNDING_BOX_EXTENSION;
  proxy.box.upperBound.x = box.upperBound.x + Settings.BOUNDING_BOX_EXTENSION;
  proxy.box.upperBound.y = box.upperBound.y + Settings.BOUNDING_BOX_EXTENSION;

  // Assign the given user Data to the proxy node.
  proxy.userData = userData;

  // Insert the proxy node on the tree.
  _insertLeaf(proxy);

  // TODO(dominich): The iteration count should be enough to hit all nodes in the 
  // tree but not too large such that it wastes time. This could be tuned.
  int iterationCount = _nodeCount &gt;&gt; 4;
  int tryCount = 0;
  int height = computeHeightFromRoot();
  while (height &gt; 64 &amp;&amp; tryCount &lt; 10) {
    rebalance(iterationCount);
    height = computeHeightFromRoot();
    ++tryCount;
  }

  return proxy;
}
</pre>
</div>
</div>
<div class="method"><h4 id="destroyProxy">
<button class="show-code">Code</button>
void <strong>destroyProxy</strong>(<a href="../box2d_html/DynamicTreeNode.html">DynamicTreeNode</a> toDestroy) <a class="anchor-link" href="#destroyProxy"
              title="Permalink to DynamicTree.destroyProxy">#</a></h4>
<div class="doc">
<p>Destroys the given proxy.</p>
<pre class="source">
void destroyProxy(DynamicTreeNode toDestroy) {
  // The given proxy must not be null and must be a leaf.
  assert(toDestroy != null);
  assert(toDestroy.isLeaf);

  // Remove and free the proxy.
  _removeLeaf(toDestroy);
  _freeNode(toDestroy);
}
</pre>
</div>
</div>
<div class="method"><h4 id="DynamicTree">
<button class="show-code">Code</button>
new <strong>DynamicTree</strong>() <a class="anchor-link" href="#DynamicTree"
              title="Permalink to DynamicTree.DynamicTree">#</a></h4>
<div class="doc">
<p>Constructs a new DynamicTree.</p>
<pre class="source">
DynamicTree() :
  _root = null,
  _nodeCount = 0,
  _insertionCount = 0,
  _path = 0,
  _lastLeaf = null,
  _drawVectors = new List&lt;Vector&gt;(4),
  _nodeCounter = 0,
  _tempVector = new Vector(),
  _tempBox = new AxisAlignedBox(),
  _nodeStack = new Queue&lt;DynamicTreeNode&gt;(),
  // Pool objects.
  center = new Vector(),
  deltaOne = new Vector(),
  deltaTwo = new Vector() {

  // Place new vectors in the draw vectors array.
  for (int i = 0; i &lt; _drawVectors.length; ++i)
    _drawVectors[i] = new Vector();
}
</pre>
</div>
</div>
<div class="method inherited"><h4 id="hashCode">
<button class="show-code">Code</button>
int <strong>hashCode</strong>() <a class="anchor-link" href="#hashCode"
              title="Permalink to DynamicTree.hashCode">#</a></h4>
<div class="inherited-from">inherited from Object </div><div class="doc">
<p>Get a hash code for this object.</p>
<p>All objects have hash codes. Hash codes are guaranteed to be the
same for objects that are equal when compared using the equality
operator <code>==</code>. Other than that there are no guarantees about
the hash codes. They will not be consistent between runs and
there are no distribution guarantees.</p>
<p>If a subclass overrides <code>hashCode</code> it should override the
equality operator as well to maintain consistency.</p>
<pre class="source">
external int hashCode();
</pre>
</div>
</div>
<div class="method"><h4 id="moveProxy">
<button class="show-code">Code</button>
bool <strong>moveProxy</strong>(<a href="../box2d_html/DynamicTreeNode.html">DynamicTreeNode</a> argProxy, <a href="../box2d_html/AxisAlignedBox.html">AxisAlignedBox</a> argBox, <a href="../box2d_html/Vector.html">Vector</a> displacement) <a class="anchor-link" href="#moveProxy"
              title="Permalink to DynamicTree.moveProxy">#</a></h4>
<div class="doc">
<p>Move a proxy with a swept AABB. If the proxy has moved outside of its
fattened AABB, then the proxy is removed from the tree and re-inserted.
Otherwise, the function returns immediately.</p>
<p>Returns true if the given proxy was re-inserted.</p>
<pre class="source">
bool moveProxy(DynamicTreeNode argProxy, AxisAlignedBox argBox,
    Vector displacement) {
  // The given proxy must not be null and must be a leaf.
  assert (argProxy != null);
  assert (argProxy.isLeaf);

  // If the given proxies box contains the given box, then return right away.
  if (argProxy.box.contains(argBox))
    return false;

  // Remove the proxy from the tree.
  _removeLeaf(argProxy);

  // Extend the bounding box.
  argBox.lowerBound.x -= Settings.BOUNDING_BOX_EXTENSION;
  argBox.lowerBound.y -= Settings.BOUNDING_BOX_EXTENSION;
  argBox.upperBound.x += Settings.BOUNDING_BOX_EXTENSION;
  argBox.upperBound.y += Settings.BOUNDING_BOX_EXTENSION;

  // Predict bounding box displacement.
  _tempVector.setFrom(displacement);
  _tempVector.mulLocal(Settings.BOUNDING_BOX_MULTIPLIER);
  if (_tempVector.x &lt; 0)
    argBox.lowerBound.x += _tempVector.x;
  else
    argBox.upperBound.x += _tempVector.x;

  if (_tempVector.y &lt; 0)
    argBox.lowerBound.y += _tempVector.y;
  else
    argBox.upperBound.y += _tempVector.y;

  argProxy.box.setFrom(argBox);

  // Insert the argument proxy and return true.
  _insertLeaf(argProxy);
  return true;
}
</pre>
</div>
</div>
<div class="method inherited"><h4 id="noSuchMethod">
<button class="show-code">Code</button>
<strong>noSuchMethod</strong>(String name, List args) <a class="anchor-link" href="#noSuchMethod"
              title="Permalink to DynamicTree.noSuchMethod">#</a></h4>
<div class="inherited-from">inherited from Object </div><div class="doc">
<p><code>noSuchMethod</code> is invoked when users invoke a non-existant method
on an object. The name of the method and the arguments of the
invocation are passed to <code>noSuchMethod</code>. If <code>noSuchMethod</code>
returns a value, that value becomes the result of the original
invocation.</p>
<p>The default behavior of <code>noSuchMethod</code> is to throw a
<code>noSuchMethodError</code>.</p>
<pre class="source">
external Dynamic noSuchMethod(String name, List args);
</pre>
</div>
</div>
<div class="method inherited"><h4 id="Object">
<button class="show-code">Code</button>
const <strong>Object</strong>() <a class="anchor-link" href="#Object"
              title="Permalink to DynamicTree.Object">#</a></h4>
<div class="inherited-from">inherited from Object </div><div class="doc">
<p>Creates a new <code>Object</code> instance.</p>
<p><code>Object</code> instances have no meaningful state, and are only useful
through their identity. An <code>Object</code> instance is equal to itself
only.</p>
<pre class="source">
const Object();
</pre>
</div>
</div>
<div class="method"><h4 id="query">
<button class="show-code">Code</button>
void <strong>query</strong>(<a href="../box2d_html/TreeCallback.html">TreeCallback</a> callback, <a href="../box2d_html/AxisAlignedBox.html">AxisAlignedBox</a> argBox) <a class="anchor-link" href="#query"
              title="Permalink to DynamicTree.query">#</a></h4>
<div class="doc">
<p>Queries a bounding box for overlapping proxies. The callback class is
called for each proxy that overlaps the given bounding box.</p>
<pre class="source">
void query(TreeCallback callback, AxisAlignedBox argBox) {
  _query(callback, argBox, _root, 1);
}
</pre>
</div>
</div>
<div class="method"><h4 id="rebalance">
<button class="show-code">Code</button>
void <strong>rebalance</strong>(int iterations) <a class="anchor-link" href="#rebalance"
              title="Permalink to DynamicTree.rebalance">#</a></h4>
<div class="doc">
<p>Rebalances the tree for the given number of iterations. Does a post-order
traversal of the tree. If given enough iterations it will hit all nodes of
the tree. Starts at the last reinserted leaf.</p>
<pre class="source">
void rebalance(int iterations) {
  if (_root == null)
    return;

  DynamicTreeNode current;
  for (int i = 0; i &lt; iterations; ++i) {
    current = _root;

    int bit = 0;
    while (!current.isLeaf) {
      int goLeft = (_path &gt;&gt; bit) &amp; 1;
      current = (goLeft == 0 ? current.childOne : current.childTwo);

      bit = (bit + 1) &amp; 31;
    }

    ++_path;

    _removeLeaf(current);
    _insertLeaf(current);
  }
}
</pre>
</div>
</div>
<div class="method inherited"><h4 id="toString">
<button class="show-code">Code</button>
String <strong>toString</strong>() <a class="anchor-link" href="#toString"
              title="Permalink to DynamicTree.toString">#</a></h4>
<div class="inherited-from">inherited from Object </div><div class="doc">
<p>Returns a string representation of this object.</p>
<pre class="source">
external String toString();
</pre>
</div>
</div>
</div>
        </div>
        <div class="clear"></div>
        </div>
        
        <div class="footer">
          
        </div>
        <script async src="../client-live-nav.js"></script>
        </body></html>
        
